package org.leetcode.middle.leetcode34;

public class Solution2 {
    public int[] searchRange(int[] nums, int target) {

        int[] res = new int[2];

        int start = search(nums, target);
        int end = search(nums, target + 1) - 1;

        if (start == nums.length || nums[start] != target) {
            res[0] = -1;
            res[1] = -1;
        } else {
            res[0] = start;
            res[1] = end;
        }

        return res;
    }

    private int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;

        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }
        return left;
    }

    private int search2(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = (left + right) >>> 1;

            if (nums[mid] < target) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                right = mid;
            }
        }

        if (left == nums.length) {
            return -1;
        }

        return nums[left]==target ? left :-1;
    }

}
